package org.dyndns.opendemogroup.optimizer.problems;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.LineNumberReader;
import java.util.HashMap;
import java.util.Random;

import org.dyndns.opendemogroup.optimizer.ArrayUtil;
import org.dyndns.opendemogroup.optimizer.ICustomCoding;
import org.dyndns.opendemogroup.optimizer.IOptimizationProblem;
import org.dyndns.opendemogroup.optimizer.Member;
import org.dyndns.opendemogroup.optimizer.Pair;

/**
 * Given a 2D graph, attempts to find the shortest tour that visits each node
 * exactly once.
 */
public class TravellingSalesmanProblem implements IOptimizationProblem,
		ICustomCoding
{

	final private int memberSize;

	final private HashMap<Integer, Pair<Double, Double>> cities;

	private double[] parameters;

	/**
	 * Parameterized constructor that will accept the list of cities as an array
	 * of &lt;cityIndex, cityX, cityY&gt; triplets, although the cityIndex will
	 * be converted to an integer and thus should be a valid integer.
	 * 
	 * @param cityList
	 *        Example value: new double[][] { { 1, 10.0, 20.0 }, { 2, 10.0, 0.0 } };
	 */
	public TravellingSalesmanProblem ( double[][] cityList )
	{
		cities = new HashMap<Integer, Pair<Double, Double>> ( );
		for ( int i = 0; i < cityList.length; i++ )
		{
			double[] c = cityList[i];
			int cityNumber = (int) c[0];
			cities.put ( cityNumber, new Pair<Double, Double> ( c[1], c[2] ) );
		}

		memberSize = cities.size ( );
		parameters = new double[memberSize];
	}

	public TravellingSalesmanProblem ( String pathToCitiesFile )
	{
		cities = new HashMap<Integer, Pair<Double, Double>> ( );
		// { load cities from pathToCitiesFile
		try
		{
			LineNumberReader reader =
				new LineNumberReader ( new FileReader ( pathToCitiesFile ) );
			String line;
			while ( ( line = reader.readLine ( ) ) != null )
			{
				// { skip "blank" lines, because the minimum is "0 0 0"
				if ( line.length ( ) < 5 )
				{
					continue;
				}
				// }
				final String[] triplet = line.split ( " ", 3 );
				final int cityNumber = Integer.parseInt ( triplet[0], 10 );
				final double x = Double.parseDouble ( triplet[1] );
				final double y = Double.parseDouble ( triplet[2] );
				cities.put ( cityNumber, new Pair<Double, Double> ( x, y ) );
			}
			reader.close ( );
		}
		catch ( FileNotFoundException fnfe )
		{
			throw new UnsupportedOperationException (
				"The file was not found, unable to proceed.", fnfe );
		}
		catch ( IOException ioe )
		{
			throw new UnsupportedOperationException (
				"Ummm...  really bad stuff happened, sorry.", ioe );
		}
		// }

		memberSize = cities.size ( );
		parameters = new double[memberSize];
	}

	/**
	 * @see IOptimizationProblem#computeFitness(Random)
	 */
	public double computeFitness ( Random randomSource )
	{
		double fitness = 0;
		for ( int i = 0; i < memberSize; i++ )
		{
			final int j = ( i + 1 ) % memberSize;
			final Pair<Double, Double> cityI =
				cities.get ( (int) parameters[i] );
			final Pair<Double, Double> cityJ =
				cities.get ( (int) parameters[j] );
			long dij =
				computeDistance ( cityI.first, cityI.second, cityJ.first,
					cityJ.second );
			fitness += dij;

		}
		return fitness;
	}

	static long computeDistance ( double xi, double yi, double xj, double yj )
	{
		double xd = xi - xj;
		double yd = yi - yj;
		long dij = Math.round ( Math.sqrt ( xd * xd + yd * yd ) );
		return dij;
	}

	/**
	 * @see IOptimizationProblem#getGeneRange()
	 */
	public int getGeneRange ( )
	{
		throw new UnsupportedOperationException (
			"Ummm... TSP doesn't use GeneRange!" );
	}

	/**
	 * @see IOptimizationProblem#getMemberSize()
	 */
	public int getMemberSize ( )
	{
		return memberSize;
	}

	/**
	 * @see IOptimizationProblem#isMaximizing()
	 */
	public boolean isMaximizing ( )
	{
		return false;
	}

	public boolean isCombinatorialOptimization ( )
	{
		return true;
	}

	public void decodeFrom ( Member source )
	{
		ArrayUtil.copy ( source.genome, parameters, 0, memberSize - 1 );
		// { adjust values by adding one (genome is 0-based, we want 1-based)
		for ( int i = 0; i < memberSize; i++ )
		{
			parameters[i]++;
		}
		// }
	}

	public void encodeTo ( Member target )
	{
		throw new UnsupportedOperationException (
			"encodeTo has bot yet been implemented!" );
	}

	public boolean makeValid ( )
	{
		// do nothing on purpose
		return false;
	}

}
